package com.jeff.question200;

import java.util.LinkedList;
import java.util.Queue;

class Position {
    int x, y, steps, candies;

    Position(int x, int y, int steps, int candies) {
        this.x = x;
        this.y = y;
        this.steps = steps;
        this.candies = candies;
    }
}

public class CandyGame {
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static int maxCandies(int N, int[][] grid, int babyX, int babyY) {
        Queue<Position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];

        queue.offer(new Position(babyX, babyY, 0, grid[babyX][babyY]));
        visited[babyX][babyY] = true;
        int maxCandy = 0;

        while (!queue.isEmpty()) {
            Position current = queue.poll();

            // 如果当前步数已经超过了最短步数，直接结束循环
            if (current.steps > maxCandy) break;

            // 更新最大糖果数
            maxCandy = Math.max(maxCandy, current.candies);

            for (int[] direction : DIRECTIONS) {
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];

                // 检查新位置是否合法
                if (newX >= 0 && newX < N && newY >= 0 && newY < N && !visited[newX][newY] && grid[newX][newY] != -1) {
                    visited[newX][newY] = true;
                    // 累加糖果数
                    int newCandies = current.candies + grid[newX][newY];
                    queue.offer(new Position(newX, newY, current.steps + 1, newCandies));
                }
            }
        }

        return maxCandy;
    }

    public static void main(String[] args) {
        int N = 3; // 地图大小
        int[][] grid = {
                {2, 3, 1},
                {1, 2, -1}, // -1 表示障碍物
                {3, 2, 1}
        };
        int babyX = 0, babyY = 0; // 宝宝位置

        System.out.println("妈妈在最短时间内最多能拿到的糖果数: " + maxCandies(N, grid, babyX, babyY));
    }
}
